#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

void helper(vector<int> &array, int si, int ei)
{
    if(si>=ei){
        return;
    }
    int pivot = si;
    int l = si + 1;
    int r = ei;

    while (l <= r)
    {
        if (array[l] > array[si] && array[r] < array[si])
        {
            swap(array[l], array[r]);
        }
        if (array[l] <= array[si])
        {
            ++l;
        }
        if (array[r] >= array[si])
        {
            --r;
        }
    }
    swap(array[pivot], array[r]);
    helper(array, si, r-1);
    helper(array, r+1, ei);
}

void quicksort(vector<int>&array){
    helper(array, 0, array.size()-1);
}

int main(int argc, char const *argv[])
{
    vector<int> zhx{8, 5, 2, 9, 6, 3};

    quicksort(zhx);
    
    for (int n : zhx)
    {
        cout << n << " ";
    }
    
    cout << endl;
    
    return 0;
}
